package problem;

import javafx.util.Pair;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class S_104 {
    //二叉树的最大深度


      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }
      //递归，dfs
    class Solution1 {
        public int maxDepth(TreeNode root) {
            if(root==null) return 0;
            int max_left=maxDepth(root.left);
            int max_right=maxDepth(root.right);
            return Math.max(max_left,max_right)+1;
        }
    }
    //用栈实现DFS

    class Solution2{
        public int maxDepth(TreeNode root){
            Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
            if (root != null) {
                stack.add(new Pair(root, 1));
            }

            int depth = 0;
            while (!stack.isEmpty()) {
                Pair<TreeNode, Integer> current = stack.pop();
                root = current.getKey();
                int current_depth = current.getValue();
                if (root != null) {
                    depth = Math.max(depth, current_depth);
                    stack.add(new Pair(root.left, current_depth + 1));
                    stack.add(new Pair(root.right, current_depth + 1));
                }
            }
            return depth;
        }
    }
}
